collection/集合框架

    3634 字
    最后修改于

    作为业务开发的工具，优秀容器框架可以很大程度上避免重复遭轮子，可以提供一些基本轻量的容器原语，方便上层实现。对于各种现代编程语言来说都是不可忽视的 / 必须要实现的，即使在某些 “大道至简” 的语言中，也有最基本的实现。在标准库中没有的往往也会被社区生态库所补充。显然，容器框架在各种实现中面临的问题必然是类似的，实现思路上也或多或少会有相似的地方。因此有必要进行一些归纳。

    集合 / 容器作为常用的工具类型，我认为可以这样总结：通过几种底层实现方式，实现一个具有某些特性（如有序、线程安全）的逻辑结构。

    实现方式：Linked、Tree、Array、Hash...
    逻辑结构：List、Queue、Set、Map...
    具有的特性：Sorted、Navigable、ConcurrentSafe、Immutable、RandomAccess...

    实现方式决定了逻辑结构具有哪些特性，为了实现某些特性，往往需要采用合适的数据结构。

    比如 Sorted/Navigable 一般通过链式 / 树结构保证。并发安全特性通常需要引入锁来实现，也有通过不可变的方式保证并发安全。RandomAccess 需要 Array 实现。

    本篇的目的则是跳出特定语言范畴以屏蔽一些不必要的底层细节，如具体的方法实现，简单概述一下各种语言中常见容器的实现思路，以及一些为了可用性可能需要的机制。

    Array/Hash#

    数组是一种具有 RandomAccess 特性的存储结构。从内存视角来看，是一块连在一起的内存。每个元素占用固定大小的内存。通过基础地址 + 偏移机制就可以做到随机访问。Hash 表底层也采用数组的形式实现快速访问。

    这种结构的快速访问性能很好，但是问题在于，数组需要固定的内存大小，容量固定，这是难以接受的。

    当然这也并不局限于数组，我们也可以规定一个固定大小的类型，从而加快访问其中的数据。
    但是内存固定的特性在提高性能的同时，也会减少动态能力。

    但多数情况下，我们既要动态特性，也要性能。
    因此对于这类底层以 Array 实现的容器类型，为了避免存储的内容达到容器上限，往往会增加动态扩容机制。

    ArrayList / 动态数组#

    常用的 List 底层一般都是 Array。尽管有用链表实现的 List，但从实际使用来看，Array 实现使用更多。在 Java 中是 ArrayList，在 python 就是 list，在 golang 中是 slice。
    当存储的元素增加达到底层数组容量时，就会触发扩容机制。

    扩容机制

    底层 Array 的扩容机制相对来说思路很简单，开辟一段新的、更大的数组内存，将原来的数据复制到新数组上即可。因此核心问题在于扩容大小的选择。

    在 Java 的 ArrayList 中，默认大小为 10（初始为 0，首次使用分配 10），默认是按增长 1.5 倍的方式进行扩容，若新容量仍不够则按当前需要的容量进行扩容。 Max(minCapacity, 1.5*oldCapacity)。这种方式较为粗暴但有效。尽管这种扩容机制使得底层 Array 可以视为无限长，但结合实际来看，为其设置一个容量上限是合理的 (Integer.MAX_VALUE)

    在 Golang 的 Slice 当中，扩容机制的容量计算在 1.17 及以前是这样的：

    1. 如果需求容量大于当前容量的两倍就会使用需求容量；
    2. 如果当前切片的长度小于 1024 就会将容量翻倍；
    3. 如果当前切片的长度大于 1024 就会每次增加 1/4 的容量，直到新容量大于期望容量；
    go
    func calculateNewCap(requireCaq, oldCap int) int {
	if requireCaq > 2 * oldCap {
		return requireCap
	}
	if oldCap < 1024 {
		return 2 * oldCap
	}
	ans := oldCap
	for requireCap > ans {
		ans += ans/4
	}
	return ans
}

    自 1.18 起，Golang 的扩容机制则进一步优化，将 2 倍扩容的限度从 1024 降至 256，增长函数也进行了调整。

    go
    func calculateNewCap(requireCaq, oldCap int) int {
	if requireCaq > 2 * oldCap {
		return requireCap
	}
	if oldCap < 256 {
		return 2 * oldCap
	}
	ans := oldCap
	for requireCap > ans {
		ans += (ans + 256 * 3)/4
	}
	return ans
}

    值得注意的是，Golang 的 Slice 扩容并不意味着底层 Array 的扩容，比如下图 B 进行扩容，可能只是涵盖[20,30,40,50]这个部分。这里讨论的是底层 Array 的扩容，但是机制是类似的。

    这种动态数组除了具有扩容机制之外，还可以引入切片机制 (sublist/slice)
    多个切片可以指向同一个底层数组的不同部分，因此对切片的更改会反映到共享同一个底层数组的其他切片上。

    HashMap / 字典#

    Map 作为 KV 键值对的映射容器，可以用来通过 key 快速的查找。实现上往往采用 Hash 表的方式。
    Hash 表是一个具有随机访问特性的连续数组。
    在构建时，显然难以预料表的容量需要多大。同样需要动态扩容。
    理想的 Hash 表的思路是通过 index = hash(key)的方式快速拿到数组索引。但是现实是 hash 冲突不可避免。而 “开放地址法” 也只是在理论上有价值。拉链法就是各个语言实现的首选。
    一般思路下，伪代码如下：

    1. hash = hashFunc(key)，计算 hash 值
    2. bucketIndex = getBucketIdx(hash)，通过hash计算出 bucketIdx
    3. bucket = getBucket(bucketIdx)，bucketIdx 获取可能所属的 bucket
    4. kvPair = findInBucket(key, hash)，通过 hash 值在 bucket 内部进一步查找所需的元素
    扩容机制

    在 Java 中，一方面，当装载因子大于一个特定值（如 0.75）时，会按照 2 次幂触发扩容，将 bucket 容量翻倍。另外一方面，当 bucket 中的链表长度大于 8 时，触发链表变换，变为红黑树。

    在 Golang 中，同样采用类似的方式进行存储。每个 bucket 中有以多个 bmap 连接而成的链表，同时每个 bmap 中最多保存 8 个 kv。操作时通过 hash 找到 bucket 之后在链表中逐个比对 topHash 和 key 值。
    当一个 bucket 中的 bmap 超过一定数量之后就进行扩容。
    扩容策略：

    1. 等量调整，当某一个 bucket 中的 bmap 链太长，进行调整，缩短 bmap 链
    2. 2 倍扩容，当装载因子太大 (大于 6.5)，进行两倍扩容，每个 bmap 都分流到两个新的 bmap 。
      扩容 / 调整的过程并非是原子的，扩容开始时会分配好新的 bucket，但是具体的数据迁移会分散到之后的每次 map 操作中。
    LinkedHashMap

    在有些实现中，通过为 HashMap 中的元素增加两个指针、将所有元素通过双向链表连接起来，形成具有插入有序的 HashMap。这种实现具有 Navigable的特性。

    Set#

    Set 作为一种不重复的集合，只需要保证值不重复好。正好，map 的 key 就是不重复的。因此在大量实现中底层都采用 hashMap，在 golang 中甚至没有可用的 set，直接推荐用 map 替代。

    Linked/Tree#

    链表、树形结构都是通过指针进行定位的，不具备 RandomAccess 的特性。相对于 Array 在内存中的紧密排布，其排布十分松散。这种实现并不可以快速访问，但是在需要修改或是频繁按条件查找的场景下会更有效。

    LinkedList / 链表#

    ... 跳过好了，这属于基本操作了，尽管理论上，链表的插入性能优秀，但是查找性能却不如 ArrayList。而且相比于 Array 实现的，因为局部性的原因（CPU Cache），实践中 ArrayList 往往也有更好的效果，在中间插入的表现也要优于 / 持平 LinkedList。Java 中的 LinkedList 作者也明确指出并不实用。

    TreeMap#

    树状 Map 的查询性能并不如 HashMap 那么快、但是可以很方便的实现有序性。Java 中采用红黑树实现，而 Rust 中使用 B 树实现（对 cache 更友好，参见：BTreeMap in std::collections - Rust (rust-lang.org)）。

    一直很不解的是 TreeMap 的实际使用场景是什么。除了有序性，似乎在性能方面会牺牲更多。（比如金融系统中按时间为 key 的股票价格？）

    TreeSet#

    类似的，TreeSet 底层往往使用 TreeMap 实现，对 TreeMap 进行了一层封装。

    Queue/Stack#

    从定义上来讲，Queue/Stack 及其变体一般只涉及在队列头尾进行操作，因此非常适合使用链式结构实现。链式结构不需要考虑扩容，应用上的特性也只需要考虑并发安全。

    PriorityQueue#

    优先队列底层一般实现也是通过大小堆实现的，本质上也是一颗树。

    关于 Iterator#

    Iterator 是迭代器，是提供给外部一个用来遍历的迭代器接口，可以屏蔽各种不同类型的细节。
    在 Java 的 Iterator 实现中，基本都会有 Fail-fast 机制，其目的只是为了让 BUG 尽可能早的显现出来（显然，在迭代时修改原有容器是不合理的）。

    并发特性#

    相比于有序，随机访问、可前后导航（Navigable）这些由底层结构就能够决定的特性，并发相对特殊一点。尽管可以通过强行遵循不可变原则强行实现集合本身的并发安全，但作为基础库而言，必然还是需要考虑可变性质的。那么就必须要引入锁的实现。
    在简单的数据结构中（如 ArrayList），可以简单的加上一把大锁保证并发安全性。在复杂的数据结构中，则可以进一步细粒度锁定，以减少锁带来的性能损失。如 golang 中的 sync.map，Java 中的ConcurrentHashMap。

    ConcurrentHashMap#

    Java 的 ConcurrentHashMap 在 1.7 -> 1.8 过程中发生了较大的变更。
    其中 1.7 版本采用分段的方式。这一层 segment 数量固定（初始化后不可变，默认 16 个），每个段中有第二层 bucket + 链表的结构。每次操作时，通过 hash 确定所在的段，每个段都有一把锁，如果并发操作不出现在同一个段内，就不会发生冲突。

    在 1.8 中则摒弃了分段的方式。采用与 1.8 中 HashMap 的 bucket + 链表 / 红黑树的思路。但仍然是对每个 bucket 进行加锁。需要对初始化 / 扩容机制进行处理。初始化采用 CAS 的方式初始化出 buckets。在扩容时，一方面需要新建 buckets、另外一方面要转移 bucket 中的内容，原来的内容一分为二、分流至新 bucket 中。
    在对 hashmap 修改时可能会进行扩容。一个线程在准备扩容时确定好大小，然后将扩容任务拆分为多个子任务，多个并发线程自行获取转移任务进行执行，转移时给 bucket 上锁。

    sync.map#

    golang 标准库中的 sync.map 底层分为 read/dirty 两个 map，通过空间换时间的思路提高并发读的性能。map 中不直接存储 kv，value 采用包装后的 entry (v) 进行操作，从而可以使得对 entry 中值的操作对两个 map 可见。

    其基本思路是将大部分读取放在 read 中利用 lock-free 加快读取 / 删除 / 更新，利用锁在 dirty 中进行写入 / 更新。具体应当结合源码查看Go 1.9 sync.Map 揭秘 (colobu.com) go/src/sync/map.go · golang/go (github.com)。

    在查找时：

    1. 先从 read 中读取，如果存在直接返回
    2. 如果不存在就给 dirty 锁，到 dirty 中查询，如果 miss 次数太多（多余 dirty），就顺便将 read 替换为 dirty，dirty 替换为 nil。（read/dirty 均为 atomic.Pointer，即使并发，这种对 read 的替换也是安全的，且此时持有锁，dirty 也是安全的）
      在插入时：
    3. 如果是个 read 中已经存在 (未标记为删除) 的 key，直接更新（atomic）。
    4. dirty 加锁
    5. 如果是个 read 中已经标记为删除的 key，在 dirty 中插入 / 更新（此处 dirty 有 key，一定被标记为删除）。
    6. 如果是个 read 中不存在的 key，在 dirty 中更新
    7. 如果 dirty 中也不存在，将 read 中没有标记为删除的键值对复制到 dirty 中，插入 dirty。
      在删除时：
    8. 如果 read 存在，直接在 read 中标记为删除 (dirty 也会受到影响，同一个 entry)，直接返回
    9. 如果 read 不存在，dirty 加锁，在 dirty 中删除。
      例如下图：
      loading...

    对 Collection 的操作#

    通过对集合中的元素进行批量变换，从 A 到 B。这是 FP 的典型应用场景。
    一些常用操作如下：
    查询：Filter、Find、Max、Min
    切分：Chunk、Take、Slice、Intersect、Distinct、Union
    分组：GroupBy、AssociateBy、PartitionBy
    断言：Any、None、All、Contains
    变换：Map、FlatMap、Windowed、Zip
    聚合：Reduce、Fold

    Stream/Sequence 机制

    一般情况下，可以通过链式调用将多个操作组合在一起，得到最终结果。
    但是这样的操作会导致多个链式调用，进行多次重复迭代，比如下面的代码，所有结果都是立即计算的，进行了两遍集合的迭代。

    kotlin
    val words = "The quick brown fox jumps over the lazy dog".split(" ")
val lengthsList = words
	.filter { it.length > 3 }
	.map { it.length }
	.take(4)


    通过引入类似 Sequence 的机制，使得多个链式调用进行组合，实现惰性计算、最终只迭代一次的目的。
    比如 Java 中的 Stream API（Spliterator）。

    kotlin
    val words = "The quick brown fox jumps over the lazy dog".split(" ")
val lengthsList = words
	.asSequence()
	.filter { it.length > 3 }
	.map { it.length }
	.take(4)
	.toList()

    其他参考#

    Why are Java Streams once-off? - Stack Overflow

    lambda - How To Use Classic Custom Data Structures As Java 8 Streams - Stack Overflow

    • 🥳0
    • 👍0
    • 💩0
    • 🤩0